1. Field of the Invention
The invention relates generally to the computer aided design of integrated circuits. More specifically, the invention relates to methods and apparatus automating the insertion of buffers during the design phase of an integrated circuit.
2. Description of the Related Art
Integrated circuits comprise a large number of circuit elements, mainly transistors, interconnected by a large number of wires. Some of the transistors (xe2x80x9cdriversxe2x80x9d) drive other circuit elements (xe2x80x9cdriven elementsxe2x80x9d). The number of drivedriven elements coupled to the output of a driver is known as the fanout of the driver.
The xe2x80x9cramptimexe2x80x9d of the driven elements coupled to a driver depends on the amount of capacitance and resistance xe2x80x9cseenxe2x80x9d by that driver, which in turn depends on the number of driven elements connected to the output of that driver and the length of the wires that interconnect the driver with its driven elements. If a driver""s load exceeds a certain threshold, the ramptime for its driven elements will also exceed a corresponding threshold, and the circuit will not function properly. To avoid this problem, during the design phase of an integrated circuit, additional drivers known as buffers are selectively inserted between drivers and driven elements.
Since each added buffer increases power consumption, it is generally desirable to minimize the number of buffers that are added. Also, since each buffer adds its own delay, it is generally desirable to minimize the number of levels of added buffers, where a single level of buffers is a set of buffers that drive other buffers or the design""s driven elements. (E.g. a buffer driving a buffer that drives a number of original driven elements corresponds to two levels of buffers.) It is also desirable to insert buffers in such a way as to minimize the overall interconnect length. Currently, buffer insertion is often performed manually; given the large number of possible buffer insertion points and the complexity of the above mentioned design goals, it is desirable to automate the location of buffer insertion points.
One proposed automated method for selecting buffer insertion points involves finding a best xe2x80x9cpathxe2x80x9d through a directed graph. A Fast Algorithm for Context-Aware Buffer Insertion, Jagannathan, Hur and Lillis, Design Automation Conference ""2000, pp. 368-373; Routing Tree Construction Under Fixed Buffer Locations, Cong and Yuan, Design Automation Conference ""2000, pp. 379-384. More particularly, a directed graph is created with a source (the original driver within a circuit), sinks (driven elements) and nodes in the graph representing possible buffer insertion points between the sources and sinks. Typically, the possible buffer insertion points are chosen randomly, subject to the floorplanning constraints of the integrated circuit (i.e. buffers can only be inserted within certain portions of the circuit). Edges connect xe2x80x9cneighboring nodesxe2x80x9d; two nodes are considered to be neighbors if the corresponding buffers (would) lie within a threshold distance that is process dependent.
The resulting graph has a large number of possible paths from the source to any sink, where each path represents a possible set of buffer insertions points and corresponding connections therebetween. Various methods are employed (Id.) to find a best path; the nodes in this best path are then the chosen buffer insertion points.
However, it is not clear how effectively the directed graph method would function for high fanout nets (e.g. nets with thousands or tens of thousands of fanouts). In particular, the computation time required to implement directed graph algorithms for high fanout nets may be unacceptably long. Further, it is no clear how well directed graph methods would achieve the previously mentioned design goals for buffer insertion methods.
In sum, there is a need for a method and apparatus that can efficiently locate buffer insertion points for high fanout nets while at least reasonably satisfying buffer insertion design goals.
To achieve the foregoing, the present invention is a method and apparatus for decreasing the ramptime of a high fanout net in an integrated circuit. The preferred method is applied after the elements comprising the circuit have been laid out but not yet connected together (i.e. the circuit has been xe2x80x9cplacedxe2x80x9d but not yet xe2x80x9croutedxe2x80x9d.)
According to an implementation of the present invention, it is determined whether a net has a ramptime violation. If so, all of the driven elements are clustered in such a manner that the total load (capacitance) of the driver decreases. The preferred clustering method minimizes the number of inserted buffers, the total interconnect length, and the number of levels of the inserted buffer tree. After clustering, one level of buffers is inserted into the net. More particularly, one buffer is inserted for each cluster created in the previously mentioned step; each of the inserted buffers drives its corresponding cluster. The buffers that are inserted will not have any ramptime violation. Therefore, each insertion of a level of buffers reduces the overall ramptime of the net.
After insertion of a level of buffers, the ramptime of the net is checked once again. If it is still not acceptable, the aforementioned clustering and insertion are repeated and the above cycle is iterated until there is no ramptime violation. During the first iteration of clustering and buffer insertion, the original circuit elements are clustered. After the first iteration of clustering and buffer insertion, the driven elements that are clustered are the buffers that were inserted in the previous iteration. In this manner, levels of buffers may be inserted into the net.
The preferred clustering method is based upon the concept of a xe2x80x9cbounding box.xe2x80x9d For any given net, a bounding box is determined according to the location of the net""s driver and the distribution of all that driver""s driven elements. A bounding box corresponds to a rectangular region within the integrated circuit in which a driver and all of its associated driven elements reside. The outer boundaries of a bounding box are defined based on the maximum x and y coordinates as well as the minimum x and y coordinates of all pins, that are not already directly driven by a buffer, connected to the net being considered (driver and all driven elements). The driven elements furthest away from the driver define the outer boundaries of the bounding box.
A bounding box, and therefore the net that it represents, may be partitioned into a plurality of regions, where once again each region corresponds to a physical region on the integrated circuit. The bounding box that contains the entire net is partitioned into four rectangular regions that all meet at the net""s driver while all other bounding boxes, which result from subsequent partitions, are partitioned from their centers into four equal sized rectangular regions. The original bounding box (region) is a xe2x80x9cparentxe2x80x9d region while the regions resulting from the partition are the xe2x80x9cchildrenxe2x80x9d of that parent. Each of the children regions may be partitioned, and so on, creating a number of levels of regions.
To perform the preferred clustering method, the bounding box of a net is determined. The bounding box is partitioned, preferably into four equal sized rectangular regions, as previously described. One of the children regions is selected and the number of driven elements therein (ND) is checked against the maximum number of allowable fanouts (MF). MF is dictated by the design rules for any particular process technology. The first time that elements are clustered, the driven elements are the original circuit elements on the integrated circuit. For each subsequent clustering, the driven elements are the buffers that were inserted during the most recent clustering.
If the number of driven elements of the selected child region (ND) is greater than the maximum number of allowable fanouts (MF), the child is partitioned iteratively until a region is found whose ND less than MF. Once such a region is located, it is expanded by adding portions of its neighboring regions until the resulting expanded region (xe2x80x9cclusterxe2x80x9d) no longer satisfies both NDcluster less than MF and Ccluster less than MC, where Ccluster is the capacitance of the cluster and MC is the maximum allowable capacitive load. Once such a cluster has been found, it is shrunk until Ccluster less than =MC. The cluster is xe2x80x9cextractedxe2x80x9d so that it is no longer subject to further clustering and a buffer is inserted into the net such that it drives the cluster.
Those portions of the cluster""s neighboring regions that were not incorporated into the cluster that was extracted are merged with all of the remaining regions at their parent""s level. In other words, all of the regions at the parent""s level are combined, except for the region that was extracted. This combined region""s ND is checked against MF, as previously described above, and the above cycle is iterated until all of the driven elements in the net have been clustered.